package leetcodev1.字符串;

import java.util.*;

public class LeetCode139 {

    public static void main(String[] args) {
        LeetCode139 leetCode139 = new LeetCode139();
        System.out.println(leetCode139.wordBreak("leetcode", Arrays.asList("leet", "code")));
    }

    //官方答案
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;//关键赋值 等于我下面的取所有 !!!牛皮 代码就很简洁了
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                //j起始位置 i终点位置
                //[j,i)字符串截取位置
                //dp[x] = x-1是否可达dp[1]代表s.substring(0, 1)是否可达
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }


    //考虑用动态规划
    //dp[i] = dp[j] && s.substring(i,j)存在
    public boolean wordBreak1(String s, List<String> wordDict) {
        int length = s.length();
        boolean[] dp = new boolean[length];
        Set<String> dict = new HashSet<>(wordDict);
        dp[0] = dict.contains(s.substring(0, 1));
        for (int i = 1; i < length; i++) {
            //直接取所有
            String substring = s.substring(0, i + 1);
            if (dict.contains(substring)) {
                dp[i] = true;
                continue;
            }

            int startIndex = 0;
            while (startIndex < i) {
                substring = s.substring(startIndex + 1, i + 1);
                if (dict.contains(substring) && dp[startIndex]) {
                    dp[i] = true;
                    break;
                }
                startIndex++;
            }
        }
        return dp[length - 1];
    }

    boolean ret = false;

    //1.枚举出list的所有集合，和s进行比较
    //2.将wordDict转换成一个散列表，然后根据切割进行比对
    //!!字典中的单词可以重复使用 看题呀
    //超出时间限制...
    public boolean wordBreak2(String s, List<String> wordDict) {
        int length = s.length();
        Set<String> dict = new HashSet<>(wordDict);
        for (int i = 1; i <= length; i++) {
            dfs(0, i, length, s, dict);
        }
        return ret;
    }

    private void dfs(int start, int end, int length, String s, Set<String> dict) {
        //结束条件
        if (ret) {
            return;
        }


        //[star,end) [0,1)
        String substring = s.substring(start, end);
        //回溯
        if (dict.contains(substring)) {
            if (end == length) {
                ret = true;
                return;
            }

            for (int i = 0; i <= length - end; i++) {
                dfs(end, end + i, length, s, dict);
            }
        }
    }
}
